Tiền thân của Phượng Hoàng là ban nhạc Hải Âu thành lập năm 1965 với thành viên chủ chốt là nhạc sĩ Lê Hựu Hà.[1] Lúc ấy, Lê Hựu Hà đã có những bản "Mai Hương", "Chiều Về", "Yêu Em", “Nhớ Thương Em Hoài” nhưng không được chú ý bởi khán giả nhạc trẻ bấy giờ chỉ thần tượng các bản nhạc ngoại quốc. Cũng như những ban nhạc kích động khác, ban Hải Âu thường biểu diễn ở những bar, club Mỹ.

Kể từ sau lần tham dự Đại hội Nhạc trẻ tổ chức năm 1966, ban Hải Âu không còn xuất hiện. Lê Hựu Hà tiếp tục kiên nhẫn sáng tác và tin tưởng rằng đến lúc nào đó sẽ đưa được nhạc trẻ lời Việt đến với công chúng.[2]

Đến đầu thập niên 1970, nhạc trẻ Sài Gòn có trào lưu “Việt hóa” các ca khúc Âu - Mỹ. Hầu hết các ban nhạc lúc bấy giờ đều hát nhạc nước ngoài và viết lời lại. Định mệnh đưa Lê Hựu Hà gặp người bạn đồng hành Nguyễn Trung Cang, nhạc sĩ của ban Rolling Sound. Năm 1971, Lê Hựu Hà cùng Nguyễn Trung Cang đứng ra thành lập ban Phượng Hoàng, chính thức ra mắt vào tối 15 tháng 6 năm 1971 tại phòng trà Đêm Màu Hồng.[2] So với các ban nhạc khác, ban nhạc Phượng Hoàng nổi bật bởi hát nhạc pop, rock thuần Việt do chính thành viên sáng tác là Lê Hựu Hà và Nguyễn Trung Cang. Bên cạnh đó, những bài hát còn được thể hiện thành công qua chất giọng đặc trưng của Elvis Phương.[3]

Năm 1973-1974, hai bài "Tôi Muốn" cùng "Yêu Người Và Yêu Đời" đã đoạt giải bài hát hay nhất giải Kim Khánh do nhật báo Trắng Đen tổ chức.

Sau sự kiện 30 tháng 4 năm 1975, ban nhạc Phượng Hoàng tan rã.[4]

Năm 2021, sách Ban nhạc Phượng Hoàng - The Beatles Sài Gòn được xuất bản nhằm tưởng nhớ ban nhạc. Lợi nhuận từ sách được dùng ủng hộ cho thành viên Nguyễn Trung Vinh.[5]